/**
 * @a https://leetcode.cn/problems/course-schedule/
 */

#include "../../common.h"


class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        unordered_map<int, vector<int>> edges(numCourses);
        vector<int> in_degree(numCourses);
        for(auto & two_tuple : prerequisites)
        {
            int dst = two_tuple[0], src = two_tuple[1];
            edges[src].push_back(dst);
            ++in_degree[dst];
        }
        
        // bfs
        queue<int> que;
        for(int i = 0; i < numCourses; ++i){
            if(in_degree[i] == 0) que.push(i);
        }
        while(que.size()){
            int out_index = que.front(); que.pop();
            for(int dst : edges[out_index]){
                --in_degree[dst];
                if(in_degree[dst] == 0) que.push(dst);
            }
        }

        for(auto degree: in_degree){
            if(degree > 0) return false;
        }
        return true;
    }
};